'''
Created on Jun 3, 2009

@author: user
'''

from cliques.potentialBasedSearch import potentialBasedSearch
import cliques.utils

class probabilisticCliqueSearch(potentialBasedSearch):
    '''
    classdocs
    '''


    def __init__(self):
        '''
        Constructor
        '''
        potentialBasedSearch.__init__(self)


    def setup(self, unknown_graph, k, start_node):
        nodes = float(len(unknown_graph.nodes()))
        edges = float(len(unknown_graph.edges()))  
        self.p =  edges/(nodes*(nodes-1)) # SHOULD DIVIDE BY 2?

        potentialBasedSearch.setup(self, unknown_graph, k, start_node) 

    def choose_node(self):

        min_expected_heuristic=float(100000)
        best_node = None
        
        # Check expected heuristic
        for node in self.generated:
            # print "Checking node %s..." % node
            # Calculate cost of all kPc
            relevant_kPc=[]
            max_core=0
            for kPc in self.pcdb:
                if len(kPc.core)>=max_core:
                    max_core = len(kPc.core)
                    if node in kPc.gcn:
                        relevant_kPc.append(kPc)
            default_value = self.k-max_core

            # Calculate node's kPc's which extending might cause a larger max core of node
            # and gather possible neighbors that may extend a relevant kPc
            possible_neighbors = set()
            removed_kPc = []
            for kPc in relevant_kPc: 
                if len(kPc.core)<max_core:
                    removed_kPc.append(kPc)
                else:
                    possible_neighbors.update(kPc.gcn)

            possible_neighbors = list(possible_neighbors)
            relevant_kPc = [item for item in relevant_kPc if item not in removed_kPc]
            
            # Calculate expected cost over all possibilities
            sum_probability = 0             
            sum_expected_heuristic = 0
            if len(relevant_kPc)>0:
                # print "Checking possible neighbors [%d]..." % len(possible_neighbors)
                for neighbors in cliques.utils.powerset(possible_neighbors):
                    for kPc in relevant_kPc:
                        
                        # Count intersection of neighbors and gcn
                        gcn_neighbors = 0
                        for neighbor in neighbors:
                            if neighbor in kPc.gcn:
                                gcn_neighbors=gcn_neighbors+1
                        
                        # If enough neighbors allow extending kPc - add it 
                        if gcn_neighbors>self.k-1-max_core:
                            probability = pow(self.p,len(neighbors))*pow(1-self.p,len(possible_neighbors)-len(neighbors))
                            sum_probability=sum_probability+ probability
                            sum_expected_heuristic = sum_expected_heuristic+probability*(default_value-1)
                            break # No point in going on relevant kPc after finding an extendable one
            
            # Add the non extended options
            sum_expected_heuristic=sum_expected_heuristic+(1-sum_probability)*default_value
            if sum_expected_heuristic<min_expected_heuristic:
                min_expected_heuristic=sum_expected_heuristic
                best_node = node
            #print "sum expected = %f (%f)" % (sum_expected_heuristic,default_value)
  
        
        # No Tie Braking
        return best_node

        
    def __str__(self):
        return "probabilisticCliqueSearch"    
